package com.sheng.leetcode.year2022.month11.day07;

import org.junit.Test;

import java.util.ArrayList;
import java.util.List;

/**
 * @author liusheng
 * @date 2022/11/07
 *<p>
 * 816. 模糊坐标<p>
 *<p>
 * 我们有一些二维坐标，如 "(1, 3)" 或 "(2, 0.5)"，然后我们移除所有逗号，<p>
 * 小数点和空格，得到一个字符串S。返回所有可能的原始字符串到一个列表中。<p>
 * 原始的坐标表示法不会存在多余的零，所以不会出现类似于"00", "0.0", "0.00", "1.0", "001",<p>
 * "00.01"或一些其他更小的数来表示坐标。此外，一个小数点前至少存在一个数，所以也不会出现“.1”形式的数字。<p>
 * 最后返回的列表可以是任意顺序的。而且注意返回的两个数字中间（逗号之后）都有一个空格。<p>
 *<p>
 * 示例 1:<p>
 * 输入: "(123)"<p>
 * 输出: ["(1, 23)", "(12, 3)", "(1.2, 3)", "(1, 2.3)"]<p>
 *<p>
 * 示例 2:<p>
 * 输入: "(00011)"<p>
 * 输出:  ["(0.001, 1)", "(0, 0.011)"]<p>
 * 解释:<p>
 * 0.0, 00, 0001 或 00.01 是不被允许的。<p>
 *<p>
 * 示例 3:<p>
 * 输入: "(0123)"<p>
 * 输出: ["(0, 123)", "(0, 12.3)", "(0, 1.23)", "(0.1, 23)", "(0.1, 2.3)", "(0.12, 3)"]<p>
 *<p>
 * 示例 4:<p>
 * 输入: "(100)"<p>
 * 输出: [(10, 0)]<p>
 * 解释:<p>
 * 1.0 是不被允许的。<p>
 *<p>
 * 提示:<p>
 * 4 <= S.length <= 12<p>
 * S[0] = "(", S[S.length - 1] = ")", 且字符串 S 中的其他元素都是数字。<p>
 */
public class LeetCode0816 {

    @Test
    public void test01() {
        String s = "(123)";
//        String s = "(00011)";
//        String s = "(0123)";
//        String s = "(100)";
        System.out.println(new Solution().ambiguousCoordinates(s));
    }
}
class Solution {
    public List<String> ambiguousCoordinates(String s) {
        s = s.substring(1, s.length() - 1);
        int length = s.length();
        List<String> list = new ArrayList<>();
        for (int i = 0; i < length - 1; i++) {
            // 枚举逗号：在 i 的后面追加逗号
            List<String> a = search(0, i, s), b = search(i + 1, length - 1, s);
            for (String s1 : a) {
                for (String s2 : b) {
                    // 循环组合坐标
                    list.add("(" + s1 + ", " + s2 + ")");
                }
            }
        }
        return list;
    }

    public List<String> search(int start, int end, String s) {
        List<String> list = new ArrayList<>();
        if (start == end || s.charAt(start) != '0') {
            list.add(s.substring(start, end + 1));
        }
        // 枚举小数点：在 i 后面追加小数点
        for (int i = start; i < end; i++) {
            // 将字符串 s 分为左右两部分
            String a = s.substring(start, i + 1), b = s.substring(i + 1, end + 1);
            // 如果左边部分长度大于 1 的同时，第一个字符为 0 那么不满足加小数点，返回
            if (a.length() > 1 && a.charAt(0) == '0') {
                continue;
            }
            // 如果右边部分的最后一个字符为 0 ，那么也不满足加小数点，返回
            if (b.charAt(b.length() - 1) == '0') {
                continue;
            }
            // 与小数点一起组合左右两部分，并添加到集合中
            list.add(a + "." + b);
        }
        return list;
    }
}
//
//作者：宫水三叶
//链接：https://leetcode.cn/problems/ambiguous-coordinates/solutions/1953924/by-ac_oier-sbxl/
//来源：力扣（LeetCode）
//著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
